package Top_Interview_Questions_Review._006Hash;



import Top_Interview_Questions_Review._006Hash.Supple.Node;
import Top_Interview_Questions_Review._006Hash.Supple.RandomListNode;

import java.util.HashMap;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/10 12:19
 * <p>
 * 功能描述:
 */
public class _0138 {

    public static void main(String[] args) {
        _0138 test = new _0138();

         Node node1 = new Node(4);
         Node node2 = new Node(7);
         Node node3 = new Node(-2);

         node1.next = node2;
         node2.next = node3;

         node1.random = node3;
         node2.random = node1;

        Node clone = test.copyRandomList(node1);
        System.out.println(clone);
    }


    /*----------------------------------O(N)空间的迭代--------------------------------------------*/

    // Visited dictionary to hold old node reference as "key" and new node reference as the "value"
    HashMap<Node, Node> visited = new HashMap<Node, Node>();

    /**
     * 还有一个O(1)空间的迭代,只看了思想,代码没看。
     */
    public Node copyRandomList(Node head) {

        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {

            // cur 老
            // map.get(cur) 新
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }


    //递归有点难懂
    /*---------------------------------------------------------------------------------------*/
    HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();

    public Node copyRandomList1(Node head) {

        if (head == null) {
            return null;
        }

        if (this.visitedHash.containsKey(head)) {
            return this.visitedHash.get(head);
        }

        Node node = new Node(head.val, null, null);

        this.visitedHash.put(head, node);


        node.next = this.copyRandomList(head.next);
        node.random = this.copyRandomList(head.random);

        return node;
    }





}
